home *** CD-ROM | disk | FTP | other *** search
/ Amiga Collections: Taifun / Taifun 029 (1987-08-15)(Ossowski, Stefan)(DE)(PD).zip / Taifun 029 (1987-08-15)(Ossowski, Stefan)(DE)(PD).adf / Utilities / FGrep / FGrep.c < prev    next >
C/C++ Source or Header  |  1978-08-10  |  23KB  |  889 lines
  1. /* FGREP.C - Search File(s) For Fixed Pattern(s)
  2.  *
  3.  * Version 1.07       November 20th, 1986
  4.  *
  5.  * Modifications:
  6.  *
  7.  *   V1.00 (84/12/01)   - beta test release
  8.  *   V1.01 (85/01/01)   - added -P option
  9.  *                      - improved command line validation
  10.  *   V1.02 (85/01/06)   - modified "run_fsa()" and "bd_move()"
  11.  *   V1.03 (85/02/11)   - added -S option
  12.  *   V1.04 (85/09/08)   - corrected "bd_go()" for UNIX
  13.  *   V1.05 (85/09/20)   - (Lloyd Rice, Computalker Consultants)
  14.  *                      - added definitions for Lattice C
  15.  *                      - linecount complemented for -CV option
  16.  *                      - buffer added for "stoupper()"
  17.  *                      - allowed for signed char representations
  18.  *   V1.06 (86/09/13)   - corrected -P option bug
  19.  *   V1.07 (86/11/20)   - added definitions for Microsoft C V4.0
  20.  *
  21.  * Copyright 1985,1986: Ian Ashdown
  22.  *                      byHeart Software
  23.  *                      620 Ballantree Road
  24.  *                      West Vancouver, B.C.
  25.  *                      Canada V7S 1W3
  26.  *
  27.  * This program may be copied for personal, non-commercial use
  28.  * only, provided that the above copyright notice is included in
  29.  * all copies of the source code. Copying for any other use
  30.  * without previously obtaining the written permission of the
  31.  * author is prohibited.
  32.  *
  33.  * Notes:
  34.  *
  35.  * The algorithm used in this program constructs a deterministic
  36.  * finite state automaton (FSA) for pattern matching from the sub-
  37.  * strings, then uses the FSA to process the text string in one
  38.  * pass. The time taken to construct the FSA is proportional to
  39.  * the sum of the lengths of the the substrings. The number of
  40.  * state transitions made by the FSA in processing the text
  41.  * string is independent of the number of substrings.
  42.  *
  43.  * Algorithm Source:
  44.  *
  45.  * "Efficient String Matching: An Aid to Bibliographic Search"
  46.  * Alfred V. Aho & Margaret J. Corasick
  47.  * Communications of the ACM
  48.  * pp. 333 - 340, Vol. 18 No. 6 (June '75)
  49.  *
  50.  * USAGE: fgrep [-vclnhyefxps] [strings] <files>
  51.  *
  52.  * where:
  53.  *
  54.  *      -v      All lines but those matching are printed.
  55.  *      -c      Only a count of the matching lines is printed.
  56.  *      -l      The names of the files with matching lines are
  57.  *              listed (once), separated by newlines.
  58.  *      -n      Each line is preceded by its line number in the
  59.  *              file.
  60.  *      -h      Do not print filename headers with output lines.
  61.  *      -y      All characters in the file are mapped to upper
  62.  *              case before matching. (This is the default if the
  63.  *              string is given in the command line under CP/M,
  64.  *              as CP/M maps everything on the command line to
  65.  *              upper case. Use the -f option if you need both
  66.  *              lower and upper case.) Not a true UNIX "fgrep"
  67.  *              option (normally available under "grep" only),
  68.  *              but too useful to leave out.
  69.  *      -e      <string>. Same as a string argument, but useful
  70.  *              when the string begins with a '-'.
  71.  *      -f      <file>. The strings (separated by newlines) are
  72.  *              taken from a file. If several strings are listed
  73.  *              in the file, then a match is flagged if any of
  74.  *              the strings are matched. If -f is given, any
  75.  *              following argument on the command line is taken
  76.  *              to be a filename.
  77.  *      -x      Only lines matched in their entirety are printed.
  78.  *      -p      Each matched line is preceded by the matching
  79.  *              substring(s). Not a UNIX "fgrep" option, but too
  80.  *              useful to leave out.
  81.  *      -s      No output is produced, only status. Used when
  82.  *              when "fgrep" is run as a process that returns a
  83.  *              status value to its parent process. Under CP/M, a
  84.  *              non-zero value returned by "exit()" may terminate
  85.  *              a submit file that initiated the program,
  86.  *              although this is implementation-dependent.
  87.  *
  88.  * DIAGNOSTICS:
  89.  *
  90.  * Exit status is 0 if any matches are found, 1 if none, 2 for
  91.  * error condition.
  92.  *
  93.  * BUGS:
  94.  *
  95.  * The following UNIX-specific option is not supported:
  96.  *
  97.  *      -b      Each line is preceded by the block number in
  98.  *              which it was found
  99.  *
  100.  * Lines are limited to 256 characters.
  101.  *
  102.  */
  103.  
  104. /*** Definitions ***/
  105.  
  106. #define TRUE               1
  107. #define FALSE              0
  108. #define MAX_LINE         257  /* Maximum number of characters */
  109.                               /* per line plus NULL delimiter */
  110. /* #define CPM */             /* Comment out for compilation */
  111.                               /* under UNIX or MS-DOS */
  112.  
  113. /* The following definitions applies to the Lattice (Version 2.15)
  114.  * and Microsoft (Version 4.0) C compilers for MS-DOS. The Lattice
  115.  * and Microsoft libraries do not have the Unix function "index()".
  116.  * However, Lattice does have an equivalent function called
  117.  * "stpchr()", and Microsoft has one called "strchr()".
  118.  */
  119.  
  120. /* #define index stpchr */    /* Remove comment delimiters for */
  121.                               /* Lattice C Version 2.15 */
  122. #define index strchr          /* Remove comment delimiters for */
  123.                               /* Microsoft C Version 4.0 */
  124.  
  125. #define CMD_ERR    0    /* Error codes */
  126. #define OPT_ERR    1
  127. #define INP_ERR    2
  128. #define STR_ERR    3
  129. #define MEM_ERR    4
  130.  
  131. /*** Typedefs ***/
  132.  
  133. typedef int BOOL;       /* Boolean flag */
  134.  
  135. /* Some C compilers, including Lattice C, do not support the
  136.  * "void" data type. Remove the following comment delimiters for
  137.  * such compilers.
  138.  */
  139.  
  140. /* typedef int void; */
  141.  
  142. /*** Data Structures ***/
  143.  
  144. /* Queue element */
  145.  
  146. typedef struct queue
  147. {
  148.   struct state_el *st_ptr;
  149.   struct queue *next_el;
  150. } QUEUE;
  151.  
  152. /* Transition element */
  153.  
  154. typedef struct transition
  155. {
  156.   char lchar;                   /* Transition character */
  157.   struct state_el *nextst_ptr;  /* Transition state pointer */
  158.   struct transition *next_el;
  159. } TRANSITION;
  160.  
  161. /* FSA state element */
  162.  
  163. typedef struct state_el
  164. {
  165.   TRANSITION *go_ls;    /* Pointer to head of "go" list */
  166.   TRANSITION *mv_ls;    /* Pointer to head of "move" list */
  167.   struct state_el *fail_state;  /* "failure" transition state */
  168.   char *out_str;        /* Terminal state message (if any) */
  169. } FSA;
  170.  
  171. /*** Global Variables and Structures ***/
  172.  
  173. /* Dummy "failure" state */
  174.  
  175. FSA FAIL_STATE;
  176.  
  177. /* Define a separate data structure for State 0 of the FSA to
  178.  * speed processing of the input while the FSA is in that state.
  179.  * Since the Aho-Corasick algorithm only defines "go" transitions
  180.  * for this state (one for each valid input character) and no
  181.  * "failure" transitions or output messages, only an array of
  182.  * "go" transition state numbers is needed. The array is accessed
  183.  * directly, using the input character as the index.
  184.  */
  185.  
  186. FSA *MZ[128];   /* State 0 of FSA */
  187.  
  188. BOOL vflag = FALSE,     /* Command-line option flags */
  189.      cflag = FALSE,
  190.      lflag = FALSE,
  191.      nflag = FALSE,
  192.      hflag = FALSE,
  193.      yflag = FALSE,
  194.      eflag = FALSE,
  195.      fflag = FALSE,
  196.      xflag = FALSE,
  197.      pflag = FALSE,
  198.      sflag = FALSE;
  199.  
  200. /*** Include Files ***/
  201.  
  202. #include <stdio.h>
  203. #include <ctype.h>
  204.  
  205. /*** Main Body of Program ***/
  206.  
  207. int main(argc,argv)
  208. int argc;
  209. char **argv;
  210. {
  211.   char *temp;
  212.   BOOL match_flag = FALSE,
  213.        proc_file();
  214.   void bd_go(),
  215.        bd_move(),
  216.        error();
  217.  
  218.   /* Check for minimum number of command line arguments */
  219.  
  220.   if(argc < 2)
  221.     error(CMD_ERR,NULL);
  222.  
  223.   /* Parse the command line for user-selected options */
  224.  
  225.   while(--argc && (*++argv)[0] == '-' && eflag == FALSE)
  226.     for(temp = argv[0]+1; *temp != '\0'; temp++)    
  227.       switch(toupper(*temp))
  228.       {
  229.         case 'V':
  230.           vflag = TRUE;
  231.           break;
  232.         case 'C':
  233.           cflag = TRUE;
  234.           break;
  235.         case 'L':
  236.           lflag = TRUE;
  237.           break;
  238.         case 'N':
  239.           nflag = TRUE;
  240.           break;
  241.         case 'H':
  242.           hflag = TRUE;
  243.           break;
  244.         case 'Y':
  245.           yflag = TRUE;
  246.           break;
  247.         case 'E':
  248.           eflag = TRUE;
  249.           break;
  250.         case 'F':
  251.           fflag = TRUE;
  252.           break;
  253.         case 'X':
  254.           xflag = TRUE;
  255.           break;
  256.         case 'P':
  257.           pflag = TRUE;
  258.           break;
  259.         case 'S':
  260.           sflag = TRUE;
  261.           break;
  262.         default:
  263.           error(OPT_ERR,NULL);
  264.       }
  265.  
  266.   /* "pflag" can only be TRUE if the following flags are FALSE */
  267.  
  268.   if(vflag == TRUE || cflag == TRUE || lflag == TRUE ||
  269.       xflag == TRUE || sflag == TRUE)
  270.     pflag = FALSE;
  271.  
  272.   /* Check for string (or string file) argument */
  273.  
  274.   if(!argc)
  275.     error(CMD_ERR,NULL);
  276.  
  277.   /* Build the "go" transitions. */
  278.  
  279.   bd_go(*argv++);
  280.   argc--;
  281.  
  282.   /* Build the "failure" and "move" transitions */
  283.  
  284.   bd_move();
  285.  
  286.   /* Process each of the input files if not "stdin". */
  287.  
  288.   if(argc < 2)
  289.     hflag = TRUE;
  290.   if(!argc)
  291.   {
  292.     if(proc_file(NULL,FALSE) == TRUE && match_flag == FALSE)
  293.       match_flag = TRUE;
  294.   }
  295.   else
  296.     while(argc--)
  297.       if(proc_file(*argv++,TRUE) == TRUE && match_flag == FALSE)
  298.         match_flag = TRUE;
  299.  
  300.   /* Return status to the parent process. Status is zero if any
  301.    * matches are found, 1 if none. 
  302.    */
  303.  
  304.   if(match_flag == TRUE)
  305.     exit(0);
  306.   else
  307.     exit(1);
  308. }
  309.  
  310. /*** Functions and Procedures ***/
  311.  
  312. /* PROC_FILE() - Run the FSA on the input file "in_file". Returns
  313.  *               TRUE if a match was found, FALSE otherwise.
  314.  */
  315.  
  316. BOOL proc_file(in_file,prt_flag)
  317. char *in_file;
  318. BOOL prt_flag;
  319. {
  320.   char buffer[MAX_LINE],        /* Input string buffer */
  321.        *bufptr,
  322.        *nl,
  323.        *index(),
  324.        *stoupper(),
  325.        *fgets();
  326.   static char ucbuf[MAX_LINE];  /* Upper case string buffer */
  327.   long line_cnt = 0L,   /* Line counter */
  328.        mtch_cnt = 0L;   /* Matched line counter */
  329.   BOOL mtch_flag,       /* Matched line flag */
  330.        run_fsa();
  331.   FILE *in_fd,
  332.        *fopen();
  333.   void error();
  334.  
  335.   if(in_file != NULL)   /* A file was specified as the input */
  336.   {
  337.     if(!(in_fd = fopen(in_file,"r")))
  338.       error(INP_ERR,in_file);
  339.   }
  340.   else
  341.     in_fd = stdin;
  342.  
  343.   /* Read in a line at a time for processing */
  344.  
  345.   while(fgets(buffer,MAX_LINE,in_fd))
  346.   {
  347.     if(nl = index(buffer,'\n'))  /* Remove newline */
  348.       *nl = '\0';
  349.     bufptr = buffer;
  350. #ifdef CPM
  351.     if(fflag == FALSE || yflag == TRUE)
  352. #else
  353.     if(yflag == TRUE)
  354. #endif
  355.     {
  356.       strcpy(ucbuf,buffer);
  357.       stoupper(bufptr = ucbuf);
  358.     }
  359.     line_cnt++;         /* Increment the line counter */
  360.     if((mtch_flag = run_fsa(bufptr)) == TRUE)
  361.       mtch_cnt++;       /* Increment matched line counter */
  362.     if(cflag == FALSE && lflag == FALSE && sflag == FALSE &&
  363.         ((mtch_flag == TRUE && vflag == FALSE) ||
  364.         (mtch_flag == FALSE && vflag == TRUE)))
  365.     {
  366.       if(hflag == FALSE && prt_flag == TRUE)
  367.         printf("%s: ",in_file);
  368.       if(nflag == TRUE)
  369.         printf("%05ld: ",line_cnt);
  370.       puts(buffer);
  371.     }
  372.   }
  373.   if(lflag == TRUE && mtch_cnt > 0)
  374.     printf("%s\n",in_file);
  375.   else if(cflag == TRUE && sflag == FALSE)
  376.   {
  377.     if(vflag == TRUE)
  378.       printf("%ld\n",line_cnt - mtch_cnt);
  379.     else
  380.       printf("%ld\n",mtch_cnt);
  381.   }
  382.   if(in_file != NULL)
  383.     fclose(in_fd);
  384.   if(mtch_cnt)          /* Match found */
  385.     return TRUE;
  386.   else                  /* No match found */
  387.     return FALSE;
  388. }
  389.  
  390. /* RUN_FSA() - Run the finite state automaton with string "str"
  391.  *             as input. Return TRUE if match, FALSE otherwise.
  392.  */
  393.  
  394. BOOL run_fsa(str)
  395. register char *str;
  396. {
  397.   register FSA *st_ptr;
  398.   BOOL msg_flag = FALSE;
  399.   FSA *go(),
  400.       *move();
  401.  
  402.   st_ptr = NULL;        /* Initialize FSA */
  403.   if(xflag == FALSE)
  404.   {
  405.     /* Process the next input character in the string */
  406.  
  407.     while(*str)
  408.     {
  409.       st_ptr = move(st_ptr,*str);
  410.  
  411.       /* Print any terminal state message */
  412.  
  413.       if(st_ptr && st_ptr->out_str)
  414.       {
  415.         msg_flag = TRUE;
  416.         if(pflag == TRUE)
  417.           printf("--> %s\n",st_ptr->out_str);
  418.         else
  419.           break;
  420.       }
  421.       str++;
  422.     }
  423.     return msg_flag;
  424.   }
  425.   else  /* Match exact lines only */
  426.   {
  427.     while(*str)
  428.     {
  429.       st_ptr = go(st_ptr,*str++);
  430.       if(!st_ptr || st_ptr == &FAIL_STATE)
  431.         return FALSE;   /* Line not matched */
  432.     }
  433.     return TRUE;        /* Exact line matched */
  434.   }
  435. }
  436.  
  437. /* GO() - Process "litchar" and return a pointer to the FSA's
  438.  *        corresponding "go" transition state. If the character
  439.  *        is not in the FSA state's "go" transition list, then
  440.  *        return a pointer to FAIL_STATE.
  441.  */
  442.  
  443. FSA *go(st_ptr,litchar)
  444. FSA *st_ptr;
  445. register char litchar;
  446. {
  447.   register TRANSITION *current;
  448.  
  449.   /* If State 0, then access separate State 0 data structure of
  450.    * the FSA. Note that there are no failure states defined for
  451.    * any input to FSA State 0.
  452.    */
  453.  
  454.   if(!st_ptr)
  455.     return MZ[litchar];
  456.   else
  457.   {
  458.     /* Point to the head of the linked list of "go" transitions
  459.      * associated with the state.
  460.      */
  461.  
  462.     current = st_ptr->go_ls;
  463.  
  464.     /* Transverse the list looking for a match to the input
  465.      * character.
  466.      */
  467.  
  468.     while(current)
  469.     {
  470.       if(current->lchar == litchar)
  471.         break;
  472.       current = current->next_el;
  473.     }
  474.  
  475.     /* Null value for "current" indicates end of list was reached
  476.      * without having found match to input character.
  477.      */
  478.  
  479.     return current ? current->nextst_ptr : &FAIL_STATE;
  480.   }
  481. }
  482.  
  483. /* MOVE() - Process "litchar" and return a pointer to the FSA's
  484.  *          corresponding "move" transition state.
  485.  */
  486.  
  487. FSA *move(st_ptr,litchar)
  488. FSA *st_ptr;
  489. register char litchar;
  490. {
  491.   register TRANSITION *current;
  492.  
  493.   /* If State 0, then access separate State 0 data structure of
  494.    * the FSA.
  495.    */
  496.  
  497.   if(!st_ptr)
  498.     return MZ[litchar];
  499.   else
  500.   {
  501.     /* Point to the head of the linked list of "move" transitions
  502.      * associated with the state.
  503.      */
  504.  
  505.     current = st_ptr->mv_ls;
  506.  
  507.     /* Transverse the list looking for a match to the input
  508.      * character.
  509.      */
  510.  
  511.     while(current)
  512.     {
  513.       if(current->lchar == litchar)
  514.         break;
  515.       current = current->next_el;
  516.     }
  517.  
  518.     /* Null value for "current" indicates end of list was reached
  519.      * without having found match to input character. The
  520.      * returned pointer is then to State 0.
  521.      */
  522.  
  523.     return current ? current->nextst_ptr : NULL;
  524.   }
  525. }
  526.  
  527. /* BD_GO() - Build the "go" transitions for each state from the
  528.  *           command-line arguments.
  529.  */ 
  530.  
  531. void bd_go(str)
  532. char *str;
  533. {
  534.   register char litchar;
  535.   char *nl,
  536.        buffer[MAX_LINE],        /* Input string buffer */
  537.        *stoupper(),
  538.        *fgets(),
  539.        *index();
  540.   FILE *str_fd,
  541.        *fopen();
  542.   void error(),
  543.        enter();
  544.  
  545.   /* Initialize FSA State 0 "go" transition array so that every
  546.    * invocation of "go()" with "state" = 0 initially returns a
  547.    * pointer to FAIL_STATE.
  548.    */
  549.  
  550.   for(litchar = 1; litchar & 127; litchar++)
  551.     MZ[litchar] = &FAIL_STATE;
  552.  
  553.   /* If the -f option was selected, get the newline-separated
  554.    * strings from the file "str" one at a time and enter them
  555.    * into the FSA. Otherwise, enter the string "str" into the
  556.    * FSA.
  557.    */
  558.  
  559.   if(fflag == TRUE)
  560.   {
  561.     if(!(str_fd = fopen(str,"r")))
  562.       error(STR_ERR,str);
  563.  
  564.     while(fgets(buffer,MAX_LINE,str_fd))
  565.     {
  566.       if(nl = index(buffer,'\n'))       /* Remove the newline */
  567.         *nl = '\0';
  568.       if(yflag == TRUE)
  569.         stoupper(buffer);
  570.       enter(buffer);
  571.     }
  572.     fclose(str_fd);
  573.   }
  574.   else
  575.   {
  576.     if(yflag == TRUE)
  577.       stoupper(str);
  578.     enter(str);
  579.   }
  580.  
  581.   /* For every input character that does not lead to a defined
  582.    * "go" transition from FSA State 0, set the corresponding
  583.    * element in the State 0 "go" transition array to indicate
  584.    * a "go" transition to State 0.
  585.    */
  586.  
  587.   for(litchar = 1; litchar & 127; litchar++)
  588.     if(MZ[litchar] == &FAIL_STATE)
  589.       MZ[litchar] = NULL;
  590. }
  591.  
  592. /* ENTER() - Enter a string into the FSA by running each
  593.  *           character in turn through the current partially-
  594.  *           built FSA. When a failure occurs, add the remainder
  595.  *           of the string to the FSA as one new state per
  596.  *           character. (Note that '\0' can never be a valid
  597.  *           character - C uses it to terminate a string.)
  598.  */
  599.  
  600. void enter(str)
  601. char *str;
  602. {
  603.   FSA *s,
  604.       *go(),
  605.       *create();
  606.   TRANSITION *current,
  607.              *insert();
  608.   char *strsave();
  609.   register char *temp;
  610.   register FSA *st_ptr = NULL;  /* Start in FSA State 0 */
  611.   register FSA *nextst_ptr;
  612.   void error();
  613.  
  614.   /* Run each character in turn through partially-built FSA until
  615.    * a failure occurs.
  616.    */  
  617.  
  618.   temp = str;
  619.   while((s = go(st_ptr,*temp)) != &FAIL_STATE)
  620.   {
  621.     temp++;
  622.     st_ptr = s;
  623.   }
  624.  
  625.   /* Process the remainder of the string */
  626.  
  627.   while(*temp)
  628.   {
  629.     /* If a new state, then create a new state and insert
  630.      * transition character and "go" transition in current
  631.      * state. (Note special case of FSA State 0.)
  632.      */
  633.  
  634.     if(!st_ptr)
  635.       nextst_ptr = MZ[*temp++] = create();
  636.     else if(!(current = st_ptr->go_ls))
  637.     {
  638.       nextst_ptr = create();
  639.       st_ptr->go_ls = insert(nextst_ptr,*temp++);
  640.     }
  641.     else
  642.     {
  643.       /* ... or it was the character that the FSA returned a
  644.        * "failure" for. Find the tail of the current state's list
  645.        * of "go" transitions, create a new state and append it
  646.        * to the current state's "go" list.
  647.        */
  648.  
  649.       while(current->next_el)
  650.         current = current->next_el;
  651.       nextst_ptr = create();
  652.       current->next_el = insert(nextst_ptr,*temp++);
  653.     }
  654.     st_ptr = nextst_ptr;
  655.   }
  656.  
  657.   /* Make string terminal state's output message */
  658.  
  659.   st_ptr->out_str = strsave(str);
  660. }
  661.  
  662. /* INSERT() - Create a new "go" transition and return a pointer
  663.  *            to it.
  664.  */
  665.  
  666. TRANSITION *insert(st_ptr,litchar)
  667. FSA *st_ptr;
  668. char litchar;
  669. {
  670.   TRANSITION *current;
  671.   char *malloc();
  672.   void error();
  673.     
  674.   if(!(current = (TRANSITION *)malloc(sizeof(TRANSITION))))
  675.     error(MEM_ERR,NULL);
  676.   current->lchar = litchar;
  677.   current->nextst_ptr = st_ptr;
  678.   current->next_el = NULL;
  679.   return current;
  680. }
  681.  
  682. /* CREATE() - Create an FSA state and return a pointer to it. */
  683.  
  684. FSA *create()
  685. {
  686.   FSA *st_ptr;
  687.   char *malloc();
  688.   void error();
  689.  
  690.   if(!(st_ptr = (FSA *)malloc(sizeof(FSA))))
  691.     error(MEM_ERR,NULL);
  692.   st_ptr->go_ls = st_ptr->mv_ls = NULL;
  693.   st_ptr->fail_state = NULL;
  694.   st_ptr->out_str = NULL;
  695.   return st_ptr;
  696. }
  697.  
  698. /* BD_MOVE() - Build the "failure" and "move" transitions for
  699.  *             each state from the "go" transitions.
  700.  */
  701.  
  702. void bd_move()
  703. {
  704.   register char litchar;
  705.   register FSA *r,      /* Temporary FSA state pointers */
  706.                *s,
  707.                *t;
  708.   FSA *go(),
  709.       *move();
  710.   TRANSITION *current,
  711.              *insert();
  712.   QUEUE *first,         /* Pointer to head of queue */
  713.         *last;          /* Pointer to tail of queue */
  714.   void add_queue(),
  715.        delete_queue();
  716.  
  717.   last = first = NULL;  /* Initialize the queue of FSA states */
  718.  
  719.   /* For each input character with a "go" transition out of FSA
  720.    * State 0, add a pointer to the "go" state to the queue. Note
  721.    * that this will also serve as the "move" transition list for
  722.    * State 0.
  723.    */
  724.  
  725.   for(litchar = 1; litchar & 127; litchar++)
  726.     if(s = go(NULL,litchar))
  727.       add_queue(&first,&last,s);
  728.  
  729.   /* While there are still state pointers in the queue, do ... */
  730.  
  731.   while(first)
  732.   {
  733.     /* Remove State "r" pointer from the head of the queue. */
  734.  
  735.     r = first->st_ptr;
  736.     delete_queue(&first);
  737.  
  738.     /* For every input to State "r" that has a "go" transition to
  739.      * State "s", do ...
  740.      */
  741.  
  742.     for(litchar = 1; litchar & 127; litchar++)
  743.     {
  744.       if((s = go(r,litchar)) != &FAIL_STATE)
  745.       {
  746.         /* If a defined "go" transition exists for State "r" on
  747.          * input "litchar", add a pointer to State "s" to the end
  748.          * of the queue.
  749.          */
  750.  
  751.         add_queue(&first,&last,s);
  752.  
  753.         /* Calculate the "failure" transition of State "s" using
  754.          * the following algorithm.
  755.          */
  756.  
  757.         t = r->fail_state;
  758.         while(go(t,litchar) == &FAIL_STATE)
  759.           t = t->fail_state;
  760.         s->fail_state = go(t,litchar);
  761.       }
  762.       else
  763.       {
  764.         /* ... otherwise set the pointer to State "s" to a
  765.          * pointer to the precalculated "move" transition of
  766.          * State "r"'s failure state on input "litchar".
  767.          */
  768.  
  769.         s = move(r->fail_state,litchar);
  770.       }
  771.  
  772.       /* Add State "s" as the "move" transition for State "r" on
  773.        * input "litchar" only if it is not State 0.
  774.        */
  775.  
  776.       if(s)
  777.         if(!r->mv_ls)   /* First instance of the list? */
  778.           current = r->mv_ls = insert(s,litchar);
  779.         else            /* No, just another one ... */
  780.           current = current->next_el = insert(s,litchar);
  781.     }
  782.   }
  783. }
  784.  
  785. /* ADD_QUEUE() - Add an instance to the tail of a queue */
  786.  
  787. void add_queue(head_ptr,tail_ptr,st_ptr)
  788. QUEUE **head_ptr,
  789.       **tail_ptr;
  790. FSA *st_ptr;
  791. {
  792.   QUEUE *pq;
  793.   char *malloc();
  794.   void error();
  795.  
  796.   /* Allocate the necessary memory and set the variables. */
  797.  
  798.   if(!(pq = (QUEUE *)malloc(sizeof(QUEUE))))
  799.     error(MEM_ERR,NULL);
  800.  
  801.   pq->st_ptr = st_ptr;
  802.   pq->next_el = NULL;
  803.  
  804.   if(!*head_ptr)        /* First instance of the queue? */
  805.     *tail_ptr = *head_ptr = pq;
  806.   else                  /* No, just another one ... */
  807.     *tail_ptr = (*tail_ptr)->next_el = pq;
  808. }
  809.  
  810. /* DELETE_QUEUE() - Delete an instance from the head of queue */
  811.  
  812. void delete_queue(head_ptr)
  813. QUEUE **head_ptr;
  814. {
  815.   *head_ptr = (*head_ptr)->next_el;
  816. }
  817.  
  818. /* STRSAVE() - Save a string somewhere in memory */
  819.  
  820. char *strsave(str)
  821. char *str;
  822. {
  823.   int strlen();
  824.   char *p,
  825.        *malloc();
  826.   void error();
  827.  
  828.   if(p = malloc(strlen(str) + 1))
  829.     strcpy(p,str);
  830.   else
  831.     error(MEM_ERR,NULL);
  832.   return p;
  833. }
  834.  
  835. /* STOUPPER() - Map entire string pointed to by "str" to upper
  836.  *              case.
  837.  */
  838.  
  839. char *stoupper(str)
  840. register char *str;
  841. {
  842.   register char *temp;
  843.  
  844.   temp = str;
  845.   while(*temp)
  846.   {
  847.     *temp = toupper(*temp);
  848.     ++temp;
  849.   }
  850.   return str;
  851. }
  852.  
  853. /* ERROR() - Error reporting. Returns an exit status of 2 to the
  854.  *           parent process.
  855.  */
  856.  
  857. void error(n,str)
  858. int n;
  859. char *str;
  860. {
  861.   fprintf(stderr,"\007\n*** ERROR - ");
  862.   switch(n)
  863.   {
  864.     case CMD_ERR:
  865.       fprintf(stderr,"Illegal command line");
  866.       break;
  867.     case OPT_ERR:
  868.       fprintf(stderr,"Illegal command line option");
  869.       break;
  870.     case INP_ERR:
  871.       fprintf(stderr,"Can't open input file %s",str);
  872.       break;
  873.     case STR_ERR:
  874.       fprintf(stderr,"Can't open string file %s",str);
  875.       break;
  876.     case MEM_ERR:
  877.       fprintf(stderr,"Out of memory");
  878.       break;
  879.     default:
  880.       break;
  881.   }
  882.   fprintf(stderr," ***\n\nUsage: fgrep [-vclnhyefxps]");
  883.   fprintf(stderr," [strings] <files>\n");
  884.   exit(2);
  885. }
  886.  
  887. /*** End of FGREP.C ***/
  888.  
  889.